L2-008 最长对称子串

题目 L2-008 最长对称子串

思路分析

回文串分为两种 一种是以奇数长度的以中间位置为中心 一种是以偶数长度的以间隙为中心

考虑清楚这两种情况 分别传入i,i 和 i,i+1 到中心拓展算法中

所谓中心拓展算法 其实就是双指针暴力

遍历每个点 以它为个中心 向左向右拓展 找到最长的回文串坐标

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

PII findLongest(const string& s,int l, int r){

	while(l>=0 && r<=s.size() && s[l]==s[r]){

		l--;

		r++;

	}

	return {l+1,r-1};

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	string s;getline(cin,s);

	int start=0,end=0;

	for(int i=0;i<s.size();i++){

		auto odd = findLongest(s,i,i);

		int left1=odd.first,right1=odd.second;

		auto even = findLongest(s,i,i+1);

		int left2=even.first,right2=even.second;

		if(right1-left1 > end-start){

			start=left1;

			end=right1;

		}

		if(right2-left2 > end-start){

			start=left2;

			end=right2;

		}

	}

	cout<<end-start+1;

	return 0;

}

同类题型

视频讲解

⬅️ L2-007 家庭房产 🏠 00-天梯赛 ➡️ L2-009 抢红包